/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-10-04
 * Time: 21:24
 */
public class Solution {

    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //核心操作
    private static void quick(int[] arr,int left,int right) {
        /*if (left >= right) {
            return;
        }*/
        if (right-left+1 <= 4) {
            insertSort(arr,left,right);
            return;
        }
        selectPivotByMedianOfThree(arr,left,right);
        int mid = findMid(arr,left,right);
        quick(arr,left,mid-1);
        quick(arr,mid+1,right);
    }
    //寻找中点
    private static int findMid(int[] arr,int left,int right) {
        int k = left;
        int tmp = arr[k];
        while (left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            while ((left < right && arr[left] <= tmp)) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,k,left);
        return left;
    }

    //交换
    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //三数取中法
    private static void selectPivotByMedianOfThree(int[] arr,int left,int right) {
        //中间元素下标
        int mid = (left+right)/2;
        if (arr[left] < arr[right]) {
            if (arr[mid] > arr[right]) {
                swap(arr,left,right);
            }else if (arr[mid] < arr[left]) {
                return;
            }else {
                swap(arr,left,mid);
            }
        }else {
            if (arr[mid] > arr[left]) {
                return;
            }else if (arr[mid] < arr[right]) {
                swap(arr,left,right);
            }else {
                swap(arr,left,mid);
            }
        }
    }

    //插入排序——快速排序专用
    private static void insertSort(int[] arr,int left,int right) {
        for (int i = left+1; i <= right; i++) {
            int j = i-1;
            int tmp = arr[i];
            for (; j >= left; j--) {
                if (arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
}
